/*
 * name: mabel xu
 * date: december 1, 2007
 * filename: BST.java (stands for Binary Search Tree)
 * description: implements a BST, with all necessary methods and helper methods to work with BST as well as a main method for testing purposes
 */

public class BST
{
	// keeps track of root of tree

	private TreeNode root;

	// default constructor, initializes root to null
	public BST()
	{
		root = null;
	}

	// returns number of nodes in tree, does not modify anything
	public int size()
	{
		return sizehelper(root);
	}

	// recursively call itself: size of tree = this one + number of nodes in left child branch + number of nodes in right child branch
	// returns 0 if is a null element (prevents infinite recursion)
	private int sizehelper(TreeNode n)
	{
		if (n == null) return 0;
		else return 1 + sizehelper(n.getLeft()) + sizehelper(n.getRight());
	}

	// if root is null, then tree is empty
	// otherwise, its not empty
	public boolean isEmpty()
	{
		return root == null;
	}

	// pre: tree can be empty or have stuff
	// post: adds object to correct place in BST
	// note: handles empty tree separate from the recursive helper
	public void add(Object o)
	{
		if (root == null) { root = new TreeNode(o, null, null); }
		else addhelper(root, o);
	}

	// when passed a treenode and an object,
	// if object less than itself, add to left (if left child null) or adds object with left child being new "self"
	// if object bigger than itself, add to right or adds object with right child being new "self"
	private void addhelper(TreeNode n, Object o)
	{
		if (o.toString().compareTo(n.getValue().toString()) <= 0)
			if (n.getLeft() == null) n.setLeft(new TreeNode(o, null, null));
			else addhelper(n.getLeft(), o);
		else	// (o.compareTo(n.getValue()) > 0)
			if (n.getRight() == null) n.setRight(new TreeNode(o, null, null));
			else addhelper(n.getRight(), o);
	}

	// returns true or false depending on if found
	public boolean find(Object o)
	{
		return findhelper(root, o);
	}

	// if self is null, then its not here
	// if self not null, then object is found as long as it equals self or either child
	private boolean findhelper(TreeNode n, Object o)
	{
		if (n == null) return false;
		else return n.getValue().equals(o) || findhelper(n.getLeft(), o) || findhelper(n.getRight(), o);
	}

	// if old object found, then try to delete and if delete successful then add new object and return true
	// if object not found or delete not successful, then return false
	public boolean replace(Object o, Object n)
	{
		if (find(o))
			if (delete(o)) { add(n); return true; }
			else return false;
		else return false;
	}

	// if root has nothing in it, then obviously u can't delete anything
	// if object is there and root is it, then do appropriate action to delete root and make link point to new root
	// if object is there and root isn't it, then use deletehelper to recursively search for and delete object
	// if none of those solutions possible, then i didn't think of it and the object didn't get deleted
	public boolean delete(Object o)
	{
		if (root == null) return false;
		else if (find(o) && root.getValue().equals(o))
		{
			if (root.getLeft() == null && root.getRight() == null)
			{
				root = null;
				return true;
			}
			else if (root.getRight() == null)
			{
				root = root.getLeft();
				return true;
			}
			else if (root.getLeft() == null)
			{
				root = root.getRight();
				return true;
			}
			else
			{
				getLastRight(root.getLeft()).setRight(root.getRight());
				root = root.getLeft();
				return true;
			}
		}
		else if (find(o)) return deletehelper(root, o);
		else return false;
	}

	// if left child is the one to delete:
	// 		if child has no children, then just delete it
	//		if child has one child, then set child of child to child
	//		if child has two children, then set left child of child as child and link right child of child to end of left child branch of child
	// if right child is the one to delete:
	// 		same thing as the other one
	// if neither children are the ones to delete, then search all children of children (using deletehelper again)
	private boolean deletehelper(TreeNode n, Object o)
	{
		if (n.getLeft() != null && n.getLeft().getValue().equals(o))
			if (n.getLeft().getLeft() == null && n.getLeft().getRight() == null) { n.setLeft(null); return true; }
			else if (n.getLeft().getRight() == null) { n.setLeft(n.getLeft().getLeft()); return true; }
			else if (n.getLeft().getLeft() == null) { n.setLeft(n.getLeft().getRight()); return true; }
			else { getLastLeft(n.getLeft().getRight()).setLeft(n.getLeft().getLeft()); n.setLeft(n.getLeft().getRight()); return true; }
		else if (n.getRight() != null && n.getRight().getValue().equals(o))
			if (n.getRight().getRight() == null && n.getRight().getLeft() == null) { n.setRight(null); return true; }
			else if (n.getRight().getRight() == null) { n.setRight(n.getRight().getLeft()); return true; }
			else if (n.getRight().getLeft() == null) { n.setRight(n.getRight().getRight()); return true; }
			else { getLastRight(n.getRight().getLeft()).setRight(n.getRight().getRight()); n.setRight(n.getRight().getLeft()); return true; }
		else
		{
			boolean temp = false;
			if (n.getLeft() != null && (n.getLeft().getLeft() != null || n.getLeft().getRight() != null)) temp = deletehelper(n.getLeft(), o);
			if (n.getRight() != null && (n.getRight().getLeft() != null || n.getRight().getRight() != null)) temp = deletehelper(n.getRight(), o);
			return temp;
		}
	}

	// just keep calling itself until you get to last one, then return that
	private TreeNode getLastLeft(TreeNode n)
	{
		if (n.getLeft() == null) return n;
		else return getLastLeft(n.getLeft());
	}

	// just keep calling itself until you get to the last one, then return that
	private static TreeNode getLastRight(TreeNode n)
	{
		if (n.getRight() == null) return n;
		else return getLastRight(n.getRight());
	}

	// use the toString I designed just for this purpose!
	public void printPreOrder()
	{
		String temp = toStringPreOrder(root);
		System.out.println(temp.substring(0, temp.length() - 2));
	}

	// prints current node, then left child node, then right child node
	// if current node is nothing, then don't add anything to the resultant string
	private String toStringPreOrder(TreeNode n)
	{
		if (n == null) return "";
		else return n.getValue().toString() + ", " + toStringPreOrder(n.getLeft()) + toStringPreOrder(n.getRight());
	}

	// use the toString i designed just for this purpose!
	public void printInOrder()
	{
		String temp = toStringInOrder(root);
		System.out.println(temp.substring(0, temp.length() - 2));
	}

	// if node is nothing, then just add nothing to string
	// if node has something, then add left child, then itself, then right child
	private String toStringInOrder(TreeNode n)
	{
		if (n == null) return "";
		else return toStringInOrder(n.getLeft()) + n.getValue().toString() + ", " + toStringInOrder(n.getRight());
	}

	// use the toString i designed just for this purpose!
	public void printPostOrder()
	{
		String temp = toStringPostOrder(root);
		System.out.println(temp.substring(0, temp.length() - 2));
	}

	// if node is nothing, add nothing to the string
	// if node has something, then add left child, then right child, then itself
	private String toStringPostOrder(TreeNode n)
	{
		if (n == null) return "";
		else return toStringPostOrder(n.getLeft()) + toStringPostOrder(n.getRight()) + n.getValue().toString()+ ", ";
	}

	// woot BST tester!
	public static void main(String[] args)
	{
		BST tree = new BST();
		tree.add(new String("M"));
		tree.add(new String("O"));
		tree.add(new String("N"));
		tree.add(new String("T"));
		tree.add(new String("G"));
		tree.add(new String("E"));
		tree.add(new String("Y"));
		tree.add(new String("C"));
		tree.add(new String("L"));
		tree.add(new String("A"));
		tree.add(new String("R"));
		tree.add(new String("F"));
		tree.add(new String("S"));
		tree.add(new String("N"));
		tree.add(new String("I"));

		System.out.println("size = " + tree.size());

		tree.printPreOrder();
		tree.printPostOrder();
		tree.printInOrder();

		tree.delete(new String("Y"));
		tree.printInOrder();
		tree.delete(new String("L"));
		tree.printInOrder();
		tree.delete(new String("M"));
		tree.printInOrder();

		tree.replace(new String("T"), new String("X"));
		tree.printInOrder();
	}		// here be the end of the main method (used for testing purposes)
}		// here be the end of the BST (i'm only adding these two comments 'cause you can't see the beginnings of these two braces from here since the screen's not long enough)